//
// 数组
//

#include <iostream>

template<typename T>
class [[maybe_unused]] GArray {
private:
    T *_list;
    int _length;
    int size;

    const int initSize = 100;
    const int incrementSize = 100;

    // 扩展数组内存大小
    void expand() {
        // 重新分配一个新的内存大小，并将原来的值拷贝
        T *newBase = (T *) std::realloc(_list, sizeof(T) * (incrementSize + size));
        if (!newBase) {
            throw std::bad_alloc();
        }
        _list = newBase;
        size += incrementSize;
    }

public:
    // 清空数组
    void clear() {
        _length = 0;
        delete[] _list;
        _list = (T *) malloc(sizeof(T) * initSize);
    }

    // 检查数组是否为空
    bool empty() {
        return _length == 0;
    }

    // 获取数组的大小
    int length() {
        return _length;
    }

    // 获取数组中的元素
    T get(int index) {
        if (index < 0 || index >= _length) {
            throw std::out_of_range("Index out of range");
        }
        return _list[index];
    }

    // 查找数组中的元素
    int find(T value) {
        for (int i = 0; i < _length; i++) {
            if (value == _list[i]) {
                return i;
            }
        }
        return -1;
    }

    // 用自定义 compare 查找数组中的元素
    // 函数对象作为参数，必须重载 Func 的 operator() 运算符
    template<typename Func>
    int get(T value, Func compare) {
        for (int index = 0; index < _length; index++) {
            if (compare(value, _list[index])) {
                return index;
            }
        }
        return -1;
    }

    // 在数组中插入元素
    void insert(int insertIndex, T value) {
        if (insertIndex < 0 || insertIndex > _length) {
            throw std::out_of_range("Index out of range");
        }
        _length += 1;
        if (_length >= size) {
            // 捕获异常并继续向外抛出
            try {
                expand();
            } catch (const std::bad_alloc &e) {
                throw e;
            }
        }
        for (int index = _length; index >= insertIndex; index--) {
            _list[index + 1] = _list[index];
        }
        _list[insertIndex] = value;
    }

    // 在数组的最后添加元素
    void append(T value) {
        insert(length(), value);
    }

    // 删除数组中的元素
    void remove(int removeIndex) {
        if (removeIndex < 0 || removeIndex >= _length) {
            throw std::out_of_range("Index out of range");
        }
        for (int index = removeIndex; index < _length - 1; index++) {
            _list[index] = _list[index + 1];
        }
        _length -= 1;
    }

    // 删除数组中的元素并返回
    T pop(int removeIndex) {
        const T value = _list[removeIndex];
        remove(removeIndex);
        return value;
    }

    // 暴力手搓迭代器
    class Iterator {
    private:
        T *_ptr;
    public:
        explicit Iterator(T *ptr) : _ptr(ptr) {}

        // 返回引用型，可以对元素进行修改
        T &operator*() {
            return *_ptr;
        }

        // 重载前置++
        Iterator &operator++() {
            _ptr++;
            return *this;
        }

        // 重载后置++
        Iterator operator++(int) {
            Iterator temp = *this;
            _ptr++;
            return temp;
        }

        bool operator!=(const Iterator &other) {
            return _ptr != other._ptr;
        }

        bool operator==(const Iterator &other) {
            return _ptr == other._ptr;
        }
    };

    Iterator begin() {
        return Iterator(_list);
    }

    Iterator end() {
        return Iterator(_list + _length);
    }

    // 遍历数组
    void traverse() {
        std::cout << "Current List:" << std::endl;
        for (auto traveler = begin(); traveler != end(); traveler++) {
            std::cout << *traveler << ' ';
        }
    }

    // 构造函数
    GArray() {
        _list = new T[initSize];
        if (!_list) {
            throw std::bad_alloc();
        }
        _length = 0;
        size = initSize;
    }

    // 析构函数
    ~GArray() {
        _length = 0;
        size = 0;
        free(_list);
    }
};
